#include <vector>
#include<algorithm>
#include<iostream>
class Solution {
public:
    const long MOD = 1e9+7;
    int nthMagicalNumber(int n, int a, int b) {
        long r = std::min(a,b)*(long)n;
        long mm = lcm(a,b);long l = 0;
        long ans =0;
        for (;l<=r;)
        {
            long mid = l+(r-l)/2;
            if(mid/a + mid/b-mid/mm >= n)
                {
                ans = mid;
                r = mid-1;
            }else
            {
                l = mid+1;
            }
        }
        return static_cast<int>(ans%MOD);
    }
  
    long gcb(long a,long b)
    {
        return b==0?a:gcb(b,a%b);
    }
    long lcm (long a, long b)
    {
        return a*b/gcb(a,b);
    }
};

